One of the basic functions in the operation of virtually all computer systems is the capability of adding two integers together. Having an addition function is essential because not only is addition used to provide numerical sums to users, it is also used in the implementation of numerous logic functions internal to the computer systems. Hence, one or more adders are typically found in the arithmetic logic unit of a computer's microprocessor.
As such, when two bits are added together, the result is a sum of those two bits plus a carry to the next, or leftward, position. Thus, the addition of multiple bits can be effectuated by using carry-out of one set of bits for carrying into the neighboring set of bits to its left. For example, the binary addition of the two bits “11” and “01” is performed by first adding together the two least significant, or rightmost, bits “1” and “1.” The result is a sum of “0” with a carry-out bit “1.” The carry-out bit is accounted for as a carry bit to the addition of the next set of bits, “0” and “1.” The result is a sum of “0” with a carry-out of “1.” This yields a final correct answer of “100” (i.e., 3+1=4).
As known to those skilled in the art, this type of adder is known as a ripple-carry adder because the addition function involves rippling the carry bit, which can be either “1” or “0,” all the way from the rightmost bit to the leftmost bit. One problem, however, associated with this type of adder is that it takes time to ripple the carry signal. In some cases, two levels of logic are implemented in computing the carry-out from a carry-in. Hence, if the least significant bit generates a carry which is propagated through the length of the adder, the signal passes through 2n levels of logic, with n being the length of the adder, before the last gate can determine whether there is a carry-out of the most significant bit. An example of such length-wide ripple effect is the addition of the binary numbers “101 . . . 111” and “000 . . . 001.”
In general, the time a circuit takes to produce an output is proportional to the maximum number of logic levels through which the signal travels, which constitutes a “critical path” of the circuit. This propagation delay is especially severe for cases involving the addition of large numbers having multiple bits, which frequently occurs in a circuit, such as a microprocessor. For example, a substantial amount of time is required to ripple a carry through the entire addition chain of two 32-bit words. Consequently, the time required to ripple the carry retards the critical time path, thereby slowing down the overall speed of the microprocessor. This detrimentally impacts the performance of a computer system.
However, ripple-carry adders are widely used in today's digital signal processing (DSP) applications because additions in these applications are most efficiently implemented using this type of adders. DSP technology serves the basis for devices such as mobile phones, multimedia computers, video recorders, CD players, etc., and will soon replace analog circuitry in television sets and telephones. Therefore, ripple-carry adders are an essential component in today's electronic devices.
Hence, it would be desirable to provide improved methods and systems for executing additions on ripple-carry adders that optimize their computational efficiency.